package com.yq.dataStructures.tree;

/**
 * @ClassName BinaryTreeDemo
 * @Description BinaryTree
 * @Author yaoqiang
 * @Date 2021/11/4 14:13
 * @Version 1.0
 */
public class BinaryTreeDemo {
    public static void main(String[] args) {
        /**
         * 创建树，创建节点，做绑定，调用三个方法
 创建树，添加节点，将节点绑定到树上，调用三种遍历的方法

 准备环节（定义节点，树，方法）：
    定义节点（属性（id,name,left,right）,方法(set,get,构造函数)）
        前序遍历（输出当前节点，如果有左边，递归调用前序，如果有有节点，递归调用右节点）。中序和后序类似。
        前序查找（看当前节点是不是，是的话返回；定局部变量存储返回值，判断左节点不为空的话递归调用，并验证上面返回的是不是，判断右节点不为空的话递归遍历确认返回值），中序后续类似
    定义树（定义一个root节点对象,）
        前序遍历（如果节点不为空，递归遍历root）
        前序查找 如果当前节点不为空，递归调用当前方法

         */
        BinaryTree binaryTree = new BinaryTree();
        HeroNode root = new HeroNode(1, "1");
        HeroNode node2 = new HeroNode(2, "2");
        HeroNode node3 = new HeroNode(3, "3");
        HeroNode node4 = new HeroNode(4, "4");
        HeroNode node5 = new HeroNode(5, "5");

        root.setLeft(node2);
        root.setRight(node3);
        node3.setLeft(node5);
        node3.setRight(node4);
        binaryTree.setHeroNode(root);

        //前序遍历12354
        binaryTree.preOrder();
        //21534
        binaryTree.infixOrder();
        //25431
        binaryTree.postOrder();
//前序查找
        HeroNode resNode = binaryTree.preOrderSearch(5);
        if (resNode != null) {
            System.out.println(resNode);
        }

        HeroNode resNode2=binaryTree.infixOrderSerarch(5);
        if (resNode2!=null){
            System.out.println(resNode2);
        }
        HeroNode resNode3=binaryTree.postOrderSearch(5);
        if (resNode3!=null){
            System.out.println(resNode3);
        }
        //前序遍历12354
        binaryTree.preOrder();
        binaryTree.delNode(5);
        binaryTree.delNode(3);
        //前序遍历12354
        binaryTree.preOrder();

    }
}

/**
 * 设置节点
 */
class HeroNode {
    public int no;
    public String name;
    public HeroNode left;
    public HeroNode right;


    /***
     * 前序遍历
     */
    public void preOrder() {
        System.out.println(this);
        if (this.left != null) {
            this.left.preOrder();
        }
        if (this.right != null) {
            this.right.preOrder();
        }
    }

    /***
     *中序遍历
     */
    public void infixOrder() {
        //前中后
        if (this.left != null) {
            this.left.infixOrder();
        }
        System.out.println(this);
        if (this.right != null) {
            this.right.infixOrder();
        }
    }

    /***
     *后序遍历
     */
    public void postOrder() {
        if (this.left != null) {
            this.left.postOrder();
        }
        if (this.right != null) {
            this.right.postOrder();
        }
        System.out.println(this);
    }


    public HeroNode(int no, String name) {
        this.no = no;
        this.name = name;
    }


    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public HeroNode getLeft() {
        return left;
    }

    public void setLeft(HeroNode left) {
        this.left = left;
    }

    public HeroNode getRight() {
        return right;
    }

    public void setRight(HeroNode right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", left=" + left +
                ", right=" + right +
                '}';
    }

    public HeroNode preOrderSearch(int i) {
        //判断当前节点是不是
        if (this.no == i) {
            return this;
        }
        HeroNode resNode = null;
        //查左子树
        if (this.left != null) {
            resNode = this.left.preOrderSearch(i);
        }
        if (resNode != null) {
            return resNode;
        }
        //查右子树
        if (this.right != null) {
            resNode = this.right.preOrderSearch(i);
        }
        return resNode;
    }
    public HeroNode infixOrderSearch(int i){
        HeroNode resNode=null;
        if (this.left!=null){
            resNode=this.left.infixOrderSearch(i);
        }
        if (resNode!=null){
            return resNode;
        }
        if (this.no==i){
            return this;
        }
        if (this.right!=null){
            resNode=this.right.infixOrderSearch(i);
        }
        return resNode;

    }

    public HeroNode postOrderSearch(int i) {
        HeroNode resNode=null;
        if (this.left!=null){
            resNode=this.left.postOrderSearch(i);
        }
        if (resNode!=null){
            return resNode;
        }
        if (this.right!=null){
            resNode=this.right.postOrderSearch(i);
        }
        if (resNode!=null){
            return resNode;
        }
        if (this.no==i){
            return this;
        }else {
            return null;
        }
    }

    public void delNode(int i) {
        if (this.left!=null && this.left.no==i){
            this.left=null;
            return;
        }
        if (this.right!=null && this.right.no==i){
            this.right=null;
            return;
        }
        if (this.left!=null){
            this.left.delNode(i);
        }
        if (this.right!=null){
            this.right.delNode(i);
        }
    }
}

class BinaryTree {
    private HeroNode root;

    public void setHeroNode(HeroNode root) {
        this.root = root;
    }

    public void preOrder() {
        if (this.root != null) {
            this.root.preOrder();
        } else {
            System.out.println("二叉树为空无法遍历");
        }
    }

    public void infixOrder() {
        if (this.root != null) {
            this.root.infixOrder();
        } else {
            System.out.println("二叉树为空无法遍历");
        }
    }

    public void postOrder() {
        if (this.root != null) {
            this.root.postOrder();
        } else {
            System.out.println("二叉树为空");
        }
    }

    public HeroNode preOrderSearch(int i) {
        if (root != null) {
            return root.preOrderSearch(i);
        } else {
            return null;
        }
    }

    public HeroNode infixOrderSerarch(int i) {
        if (root!=null){
            return this.root.infixOrderSearch(i);
        }else {
            return  null;
        }
    }

    public HeroNode postOrderSearch(int i) {
        if (root!=null){
            return this.root.postOrderSearch(i);
        }else {
            return null;
        }
    }

    public void delNode(int i) {
        if (root!=null){
            if (root.no==i){
                root=null;
            }else {
                root.delNode(i);
            }
        }else {
            System.out.println("null tree ");
        }
    }
}